package solutions.leetcode.hard;

import solutions.lib.BaseSolution;

import java.util.Calendar;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/count-vowels-permutation/">1220.统计元音字母序列的数目</a>
 */
public class Solution1220 extends BaseSolution {

    public int countVowelPermutation(int n) {
        int mod = (int) (10E8 + 7);
        int[][] f = {
                {1, 1, 1, 1, 1},
                {0, 0, 0, 0, 0}
        };
        int now = 0;

        while (--n > 0) {
            f[1 - now][0] = ((f[now][1] + f[now][2]) % mod + f[now][4]) % mod;
            f[1 - now][1] = (f[now][0] + f[now][2]) % mod;
            f[1 - now][2] = (f[now][1] + f[now][3]) % mod;
            f[1 - now][3] = f[now][2];
            f[1 - now][4] = (f[now][2] + f[now][3]) % mod;
            now = 1 - now;
        }

        int r = 0;
        for (int v : f[now]) {
            r += v;
            r %= mod;
        }
        return r;
    }

    public static void main(String[] args) {
        Solution1220 solution = new Solution1220();
        for (int i = 1; i < 10; i++) {
            int r = solution.countVowelPermutation(i);
            System.out.println(r);
        }

        System.out.println();
        long start = Calendar.getInstance().getTimeInMillis();
        System.out.println(solution.countVowelPermutation(20000));
        System.out.println(Calendar.getInstance().getTimeInMillis() - start);
    }
}